{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #不同的子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code><strong> </strong>和一个字符串 <code>t</code> ，计算在 <code>s</code> 的子序列中 <code>t</code> 出现的个数。</p>\n",
    "\n",
    "<p>字符串的一个 <strong>子序列</strong> 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，<code>&quot;ACE&quot;</code>&nbsp;是&nbsp;<code>&quot;ABCDE&quot;</code>&nbsp;的一个子序列，而&nbsp;<code>&quot;AEC&quot;</code>&nbsp;不是）</p>\n",
    "\n",
    "<p>题目数据保证答案符合 32 位带符号整数范围。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;rabbbit&quot;, t = &quot;rabbit&quot;<code>\n",
    "<strong>输出</strong></code><strong>：</strong><code>3\n",
    "</code><strong>解释：</strong>\n",
    "如下图所示, 有 3 种可以从 s 中得到 <code>&quot;rabbit&quot; 的方案</code>。\n",
    "<code><strong><u>rabb</u></strong>b<strong><u>it</u></strong></code>\n",
    "<code><strong><u>ra</u></strong>b<strong><u>bbit</u></strong></code>\n",
    "<code><strong><u>rab</u></strong>b<strong><u>bit</u></strong></code></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;babgbag&quot;, t = &quot;bag&quot;\n",
    "<code><strong>输出</strong></code><strong>：</strong><code>5\n",
    "</code><strong>解释：</strong>\n",
    "如下图所示, 有 5 种可以从 s 中得到 <code>&quot;bag&quot; 的方案</code>。 \n",
    "<code><strong><u>ba</u></strong>b<u><strong>g</strong></u>bag</code>\n",
    "<code><strong><u>ba</u></strong>bgba<strong><u>g</u></strong></code>\n",
    "<code><u><strong>b</strong></u>abgb<strong><u>ag</u></strong></code>\n",
    "<code>ba<u><strong>b</strong></u>gb<u><strong>ag</strong></u></code>\n",
    "<code>babg<strong><u>bag</u></strong></code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length, t.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 115&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/distinct-subsequences/\">https://leetcode-cn.com/problems/distinct-subsequences/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [21dk04](https://leetcode.cn/problems/21dk04/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [21dk04](https://leetcode.cn/problems/21dk04/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "\n",
    "        # d[i][j] means the s[i] match t[j]'s count \n",
    "\n",
    "        # aabaabaa\n",
    "        # aba\n",
    "\n",
    "        #    0a    1b    2a\n",
    "        # 0a  1    0     0\n",
    "        # 1a  1    0     0\n",
    "        # 2b  2    \n",
    "        # 3a  2\n",
    "        # 4a  \n",
    "        # 5b  0\n",
    "        # 7a  \n",
    "        # 7a\n",
    "\n",
    "        sl = len(s)\n",
    "        tl = len(t)\n",
    "        # d = [[0 for _ in range(tl)] for _ in range(sl) ]\n",
    "\n",
    "        # for i in range(sl):\n",
    "        #     if s[i] == t[0]:\n",
    "        #         d[i][0] = 1\n",
    "        \n",
    "        # for j in range(tl):\n",
    "        #     if s[0] == t[i]:\n",
    "        #         d[0][i] = 1\n",
    "        \n",
    "        # for i in range(1, sl):\n",
    "        #     for j in range(1, tl):\n",
    "        #         if \n",
    "\n",
    "        pd = defaultdict(list)\n",
    "        for i, c in enumerate(t):\n",
    "            pd[c].append(i)\n",
    "\n",
    "        for _, arr in pd.items():\n",
    "            arr.reverse()\n",
    "\n",
    "        d = [0] * tl\n",
    "        for c in s:\n",
    "            for p in pd[c]: \n",
    "                if p == 0:\n",
    "                    d[0] += 1\n",
    "                \n",
    "                else:\n",
    "                    d[p] += d[p-1]\n",
    "        \n",
    "        return d[tl - 1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        self.s = s\n",
    "        self.t = t\n",
    "        self.len_s = len(s)\n",
    "        self.len_t = len(t)\n",
    "        re = self.dp(0,0)\n",
    "        return re\n",
    "    \n",
    "    @lru_cache()\n",
    "    def dp(self,i,j):\n",
    "        if self.len_s-i<self.len_t-j:\n",
    "            return 0\n",
    "        if j==self.len_t:\n",
    "            return 1\n",
    "        if self.s[i]==self.t[j]:\n",
    "            return self.dp(i+1,j+1)+self.dp(i+1,j)\n",
    "        elif self.s[i]!=self.t[j]:\n",
    "            return self.dp(i+1,j)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from pprint import pprint\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "\n",
    "        if m < n:\n",
    "            return 0\n",
    "\n",
    "        if m == n and s != t:\n",
    "            return 0\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(j, m+1):\n",
    "                print(i, j, s[i-1], t[j-1])\n",
    "                if s[i-1] != t[j-1]:\n",
    "                    if i == j:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]\n",
    "        pprint(dp)\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s)<len(t) :\n",
    "            return 0\n",
    "        if t==\"\" :\n",
    "            return 0\n",
    "        if len(t)==1 :\n",
    "            return s.count(t)\n",
    "        \n",
    "        # 经过上面的对特殊情况的处理, 已经保证 t 中至少包含2个字符，且 s 的长度不小于 t . \n",
    "        \n",
    "        vocab = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        vocab += vocab.upper()\n",
    "        s_index_list = dict( [ (i,[]) for i in vocab ] )\n",
    "        \n",
    "        for i,symbol in enumerate(s,start=0) :\n",
    "            s_index_list[symbol].append(i)\n",
    "            \n",
    "        t_index_list = dict( [ (i,[]) for i in range(len(t)) ] )\n",
    "        \n",
    "        for i,symbol in enumerate(t,start=0) :\n",
    "            temp = s_index_list[symbol]\n",
    "            if temp == [] :\n",
    "                return 0\n",
    "            else:\n",
    "                t_index_list[i].extend(temp)\n",
    "        \n",
    "        left_ptr = dict( [ (i,0) for i in range(len(t)) ] )\n",
    "        right_ptr = dict( [ (i,len(t_index_list[i])) for i in range(len(t)) ] )\n",
    "        \n",
    "        for i in range(1,len(t),1) :\n",
    "            for j,index in enumerate(t_index_list[i],start=0) :\n",
    "                if index > t_index_list[i-1][left_ptr[i-1]] :\n",
    "                    left_ptr[i] = j\n",
    "                    break\n",
    "                if j == len(t_index_list[i])-1 :\n",
    "                    return 0\n",
    "        \n",
    "        for i in range(len(t)-2,-1,-1) :\n",
    "            for j,index in enumerate(t_index_list[i][::-1],start=len(t_index_list[i])) :\n",
    "                if index < t_index_list[i+1][len(t_index_list[i+1])-1] :\n",
    "                    right_ptr[i] = j\n",
    "                    break\n",
    "        \n",
    "        count_list = dict( [ (i,[]) for i in range(len(t)) ] )\n",
    "        for i in range(len(t)-1,-1,-1) :\n",
    "            if i == len(t)-1 :\n",
    "                for _ in range(0,len(t_index_list[i][left_ptr[i]:right_ptr[i]]),1) :\n",
    "                    count_list[i].append(1)\n",
    "            else :\n",
    "                for index in t_index_list[i][left_ptr[i]:right_ptr[i]] :\n",
    "                    count = 0\n",
    "                    for j,index_ in enumerate(t_index_list[i+1][left_ptr[i+1]:right_ptr[i+1]],start=0) :\n",
    "                        if index_>index :\n",
    "                            count += count_list[i+1][j]\n",
    "                    count_list[i].append(count)\n",
    "        \n",
    "        return sum(count_list[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = {}\n",
    "        return self.mym(s,t,0,0,m)\n",
    "    def mym(self, s,t,i,j,m):\n",
    "        if (i,j) in m:\n",
    "            return m[(i,j)]\n",
    "        if j == len(t):\n",
    "            m[(i,j)] = 1\n",
    "        elif len(s) - i < len(t) - j:\n",
    "            m[(i,j)] = 0\n",
    "\n",
    "        elif s[i] == t[j]:\n",
    "            m[(i,j)]= self.mym(s,t,i+1,j+1,m) + self.mym(s,t,i+1,j,m)\n",
    "        else:\n",
    "            m[(i,j)] = self.mym(s,t,i+1,j,m)\n",
    "        return m[(i,j)]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "\n",
    "        vst = {}\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in vst: return vst[(i, j)]\n",
    "            if j == len(t): return 1\n",
    "            if len(s)-i < len(t)-j : return 0\n",
    "\n",
    "            cnt = 0\n",
    "            cnt += dfs(i+1, j)\n",
    "\n",
    "            if s[i] == t[j]:\n",
    "                cnt += dfs(i+1, j+1)\n",
    "\n",
    "            vst[(i, j)] = cnt\n",
    "\n",
    "            return cnt\n",
    "        \n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        self.s = s\n",
    "        self.t = t\n",
    "        self.len_s = len(s)\n",
    "        self.len_t = len(t)\n",
    "        re = self.dp(0,0)\n",
    "        return re\n",
    "    \n",
    "    @cache\n",
    "    def dp(self,i,j):\n",
    "        if self.len_s-i<self.len_t-j:\n",
    "            return 0\n",
    "        if j==self.len_t:\n",
    "            return 1\n",
    "        if self.s[i]==self.t[j]:\n",
    "            return self.dp(i+1,j+1)+self.dp(i+1,j)\n",
    "        elif self.s[i]!=self.t[j]:\n",
    "            return self.dp(i+1,j)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        # self.memory = [[-1 for i_t in range(len(t))] for i_s in range(len(s))]\n",
    "        return self.dp(s, 0, t, 0)\n",
    "    \n",
    "    @cache\n",
    "    def dp(self, s, i, t, j):\n",
    "        if j == len(t):\n",
    "            return 1\n",
    "        if len(s) - i < len(t) - j:\n",
    "            return 0\n",
    "        \n",
    "        # if self.memory[i][j] != -1:\n",
    "        #     return self.memory[i][j]\n",
    "        \n",
    "        res = 0\n",
    "        if s[i] == t[j]:\n",
    "            res += self.dp(s, i+1, t, j+1) + self.dp(s, i+1, t, j)\n",
    "        else:\n",
    "            res += self.dp(s, i+1, t, j)\n",
    "        \n",
    "        # self.memory[i][j] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        lens, lent = len(s), len(t)\n",
    "        count = 0\n",
    "        # 先找到第1个匹配子序列,并将所匹配的s中的索引记录下来\n",
    "        ps, pt = 0, 0\n",
    "        sindexs = [0] * lent\n",
    "        while ps < lens and pt < lent:\n",
    "            while ps < lens and pt < lent and s[ps] == t[pt]:\n",
    "                sindexs[pt] = ps\n",
    "                ps += 1\n",
    "                pt += 1\n",
    "            ps += 1\n",
    "        if pt == lent:  # 找到了第1个匹配位置，将数量设置为1\n",
    "            count = 1\n",
    "        else:\n",
    "            return 0\n",
    "        # 记忆数组\n",
    "        dp = [[-1] * (lens + 1) for i in range(lens + 1)]\n",
    "\n",
    "        # 回溯查找所有可能的匹配组合,先在s中查找t的最右边字符，查找方向为从目前已匹配位置到右侧边界。然后查找次右边字符\n",
    "        def backtrack(index, end):\n",
    "            if dp[index][end] >= 0:  # 如果记忆数组中已经有结果，直接返回\n",
    "                return dp[index][end]\n",
    "            cnt = 0\n",
    "            for i in range(sindexs[index] + 1, end):\n",
    "                if s[i] == t[index]:  # 找到一个匹配\n",
    "                    cnt += 1\n",
    "                    if index > 0:  # 如果不是t的第1个字符，需要继续搜索\n",
    "                        cnt += backtrack(index - 1, i)\n",
    "            if index > 0:  # 该字符不动，尝试移动前面的字符进行匹配\n",
    "                cnt += backtrack(index - 1, sindexs[index])\n",
    "            dp[index][end] = cnt\n",
    "            return cnt\n",
    "\n",
    "        return count + backtrack(lent - 1, lens)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        self.memo = [[-1]*len(t) for _ in range(len(s))]\n",
    "        return self.dp(s, 0, t, 0)\n",
    "       \n",
    "\n",
    "    def dp(self,s,i,t,j):\n",
    "        if j == len(t):\n",
    "            return 1\n",
    "        if len(s)-i<len(t)-j:\n",
    "            return 0\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        res = 0\n",
    "        for k in range(i,len(s)):\n",
    "            if s[k] == t[j]:\n",
    "                res += self.dp(s, k+1, t, j+1)\n",
    "        self.memo[i][j] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        memo = [[-1]*n for _ in range(m)]\n",
    "\n",
    "        return self.dp(s, 0, t, 0, memo)\n",
    "\n",
    "    def dp(self, s, i, t, j, memo):\n",
    "        m, n = len(s), len(t)\n",
    "        if j == n:\n",
    "            return 1\n",
    "        \n",
    "        if n - j > m - i:\n",
    "            return 0\n",
    "        \n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "        \n",
    "        res = 0\n",
    "        if s[i] == t[j]:\n",
    "            res += self.dp(s, i+1, t, j+1, memo) + self.dp(s, i+1, t, j, memo)\n",
    "        else:\n",
    "            res += self.dp(s, i+1, t, j, memo)\n",
    "        \n",
    "        memo[i][j] = res \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-2526f/\n",
    "# 手机微信有文章\n",
    "# 方法一：站在t的角度（盒子），让盒子去选球（s）\n",
    "# 备忘录方法。消除重叠子序列问题\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) == 0 or len(t) == 0:\n",
    "            return 0\n",
    "        # 找最长的个数，那么初始化就要初始化个很小的值，永远取不到的小值就可以了。0是可能成为最终答案的，但-1不可能\n",
    "        m, n = len(s), len(t)\n",
    "        # memo的定义：memo[i][j]指的是，截止到s[i]，找到t中元素（累计。截止到t[j]元素）的个数\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        return self.dp(memo, s, 0, t, 0)\n",
    "    \n",
    "    def dp(self, memo, s, i, t, j):\n",
    "        # base case 1\n",
    "        if j == len(t): # j最大= len(t) -1,如果等于len(t)，说明上一步的j=len(t)-1已经在s中找到了，所以才会发生j再+1=len(t)的情况\n",
    "            return 1\n",
    "\n",
    "        # base case 2: 剪枝\n",
    "        if len(s) - i < len(t) - j:\n",
    "            return 0\n",
    "        \n",
    "        # 查备忘录防止冗余计算\n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "\n",
    "        # 状态转移\n",
    "        # for 状态 in 状态列表\n",
    "        res = 0\n",
    "        for k in range(i, len(s)):\n",
    "            if s[k] == t[j]:\n",
    "                # 累加结果\n",
    "                # 只有找到了t中全部字符，这里的res才会被+1\n",
    "                # 比如说，s[5]的时候就已经找到了所有t字符，那么就返回1，res就加1，加完1后，又开始正常循环，这里是指最外层循环，下一个k，比如改循环k=1了\n",
    "                res += self.dp(memo, s, k+1, t, j+1) \n",
    "        \n",
    "        # memo的定义：从s[i]开始找，一直找到s的最后一个数。找什么呢？找t[j] t[j+1]，一直到t的最后一个数。\n",
    "        # 在s[i]及以后的字符中，找到了全部t[j]及以后的字符。找到了全部t[j]及以后的字符，找到了几次呢？这个几次就是memo的值\n",
    "        memo[i][j] = res\n",
    "\n",
    "        return res\n",
    "\n",
    "# 方法二：站在s的角度，让球去选盒子（t)。理解方法一就行\n",
    "# 备忘录方法\n",
    "# class Solution:\n",
    "#     def numDistinct(self, s: str, t: str) -> int:\n",
    "#         if len(s) == 0 or len(t) == 0:\n",
    "#             return 0\n",
    "#         m, n = len(s), len(t)\n",
    "#         memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "#         return self.dp(memo, s, 0, t, 0)\n",
    "\n",
    "#     def dp(self, memo, s, i, t, j):\n",
    "#         # base case 1\n",
    "#         if j == len(t):\n",
    "#             return 1\n",
    "        \n",
    "#         # base case 2\n",
    "#         if len(s) - i < len(t) - j:\n",
    "#             return 0\n",
    "        \n",
    "#         # 查询备忘录防止重叠子问题\n",
    "#         if memo[i][j] != -1:\n",
    "#             return memo[i][j]\n",
    "        \n",
    "#         # 状态转移\n",
    "#         res = 0\n",
    "#         if s[i] == t[j]:\n",
    "#             res += self.dp(memo, s, i+1, t, j+1) + self.dp(memo, s, i+1, t, j)\n",
    "#         else:\n",
    "#             res += self.dp(memo, s, i+1, t, j)\n",
    "        \n",
    "#         # 记进备忘录\n",
    "#         memo[i][j] = res\n",
    "\n",
    "#         return memo[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        memo = [[-1 for _ in range(m)] for _ in range(n)]\n",
    "        \n",
    "        def dp(i, j):\n",
    "            #找到t字符串的末尾了，说明t整个序列都匹配到了\n",
    "            if j == len(t):\n",
    "                return 1\n",
    "            \n",
    "            #如果s剩余的序列比t还短，就不可能找到了\n",
    "            if n-i < m-j:\n",
    "                return 0\n",
    "            \n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            memo[i][j] = 0\n",
    "            #如果当前字符匹配\n",
    "            if s[i] == t[j]:\n",
    "                #把当前字符加入结果序列，然后在当前字符后面继续找\n",
    "                #或者丢弃当前字符，然后在当前字符后面继续找\n",
    "                memo[i][j] = dp(i+1, j+1)+dp(i+1, j)\n",
    "            else:\n",
    "                memo[i][j] = dp(i+1, j)\n",
    "                \n",
    "            return memo[i][j]\n",
    "        \n",
    "        dp(0, 0)\n",
    "        return memo[0][0] if memo[0][0] != -1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        @cache\n",
    "        def num(x, y):\n",
    "            if len(y) > len(x): return 0\n",
    "            if y == '': return 1\n",
    "            if len(x) == len(y):\n",
    "                if x == y: return 1\n",
    "                return 0\n",
    "            ans = num(x[1:], y)\n",
    "            if x[0] == y[0]: ans += num(x[1:], y[1:])\n",
    "            return ans\n",
    "        return num(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        N, M = len(s), len(t)\n",
    "        if N==0 and M==0 : return 1\n",
    "\n",
    "        tset = set(t)\n",
    "        news =''\n",
    "        for c in s:\n",
    "            if c in tset:\n",
    "                news +=c\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(s,t):  \n",
    "            N, M = len(s), len(t)\n",
    "            if N==0 and M==0 : return 1 # todo\n",
    "            if M>N: return 0\n",
    "            if s==t : return 1\n",
    "            if M==0: return 1 # todo\n",
    "            re = 0\n",
    "            if s[0] == t[0]:\n",
    "                re += dfs(s[1:], t[1:])\n",
    "            re += dfs(s[1:], t)\n",
    "            return re\n",
    "\n",
    "        \n",
    "        return dfs(s,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        \"\"\"\n",
    "        s = \"babgbag\", t = \"bag\"\n",
    "        s = \"rabbbit\", t = \"rabbit\"\n",
    "        :param s:\n",
    "        :param t:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len(s) == 0 and len(t) == 0:\n",
    "            return 1\n",
    "        if len(t) == 0 and len(s) > 0:\n",
    "            return 1\n",
    "        if len(s) < len(t):\n",
    "            return 0\n",
    "        if len(s) == len(t):\n",
    "            if s == t:\n",
    "                return 1\n",
    "            return 0\n",
    "        if s[0] != t[0]:\n",
    "            return self.numDistinct(s[1:], t)\n",
    "        v1 = self.numDistinct(s[1:], t[1:])\n",
    "        v2 = self.numDistinct(s[1:], t)\n",
    "        return v1 + v2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        self.memory = [[-1 for i_t in range(len(t))] for i_s in range(len(s))]\n",
    "        return self.dp(s, 0, t, 0)\n",
    "    \n",
    "    @cache\n",
    "    def dp(self, s, i, t, j):\n",
    "        if j == len(t):\n",
    "            return 1\n",
    "        if len(s) - i < len(t) - j:\n",
    "            return 0\n",
    "        \n",
    "        if self.memory[i][j] != -1:\n",
    "            return self.memory[i][j]\n",
    "        \n",
    "        res = 0\n",
    "        if s[i] == t[j]:\n",
    "            res += self.dp(s, i+1, t, j+1) + self.dp(s, i+1, t, j)\n",
    "        else:\n",
    "            res += self.dp(s, i+1, t, j)\n",
    "        \n",
    "        self.memory[i][j] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(t) > len(s):\n",
    "            return 0 \n",
    "        if len(t) == len(s):\n",
    "            return 1 if t==s else 0\n",
    "        \n",
    "        import numpy as np\n",
    "        dp = np.zeros((len(s), len(t))).astype('int')\n",
    "        if s[0] == t[0]:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            dp[i][0] = dp[i - 1][0] + (1 if s[i] == t[0] else 0)\n",
    "        for j in range(1, len(t)):\n",
    "            for i in range(len(s)):\n",
    "                if i < j:\n",
    "                    dp[i][j] = 0\n",
    "                elif i == j:\n",
    "                    dp[i][j] = 1 if s[:i+1] == t[:j+1] else 0\n",
    "                else:\n",
    "                    if s[i] == t[j]:\n",
    "                        dp[i][j] = dp[i-1][j] + dp[i-1][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "        return int(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        buffer = np.zeros(len(s), dtype = np.int32)\n",
    "        for i, char in enumerate(s):\n",
    "            if char == t[0]:\n",
    "                buffer[i] = 1\n",
    "        j = 1\n",
    "        while j < len(t) and np.any(buffer):\n",
    "            print(buffer)\n",
    "            for i in range(len(s) - 1, j - 1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    buffer[i] = np.sum(buffer[:i])\n",
    "                else:\n",
    "                    buffer[i] = 0\n",
    "            buffer[:j] = 0\n",
    "            \n",
    "            j += 1\n",
    "\n",
    "        # print(buffer)\n",
    "\n",
    "        # for i in range(len(s)):\n",
    "        #     for j in range(1, len(t)):\n",
    "        #         if s[i] == t[j]:\n",
    "        #             buffer[i, j] = sum(buffer[:i, j - 1])\n",
    "        \n",
    "        # print(buffer)\n",
    "        return int(sum(buffer))\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n, m = len(t), len(s)\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        \n",
    "        for j in range(m + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "\n",
    "            temp = 0\n",
    "            while temp < m and dp[i - 1][temp] == 0:\n",
    "                temp += 1 \n",
    "\n",
    "            for j in range(temp + 1, m + 1):\n",
    "                if t[i - 1] == s[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j-1] +  dp[i][j - 1]\n",
    "                    dp[i][j] %= mod\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        if m < n or m == 0 or n == 0:\n",
    "            return 0\n",
    "        dp = [[0]*min(i+1, n) for i in range(m)]\n",
    "        # dp[i][j] 表示 s[0...i] 中 t[0...j] 出现的个数\n",
    "        for i in range(m):\n",
    "            for j in range(min(i+1, n)):\n",
    "                if i == j:\n",
    "                    dp[i][j] = int(s[:i+1] == t[:j+1])\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + int(s[i] == t[j])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i] == t[j] else 0)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t): return 0\n",
    "        dp = [[0] * min(i + 1, len(t) + 1) for i in range(len(s) + 1)]\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][0] = 1\n",
    "        \n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[i])):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + (dp[i - 1][j] if j < len(dp[i - 1]) else 0)\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] if j < len(dp[i - 1]) else 0\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        ans_dict = {}\n",
    "        def num_distinct(i, j):\n",
    "            key = i * 1000 + j\n",
    "            if key in ans_dict:\n",
    "                return ans_dict[key]\n",
    "            if j == len(t):\n",
    "                ans_dict[key] = 1\n",
    "                return 1\n",
    "            if len(s) - i < len(t) - j:\n",
    "                ans_dict[key] = 0\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for iii in range(i, len(s)):\n",
    "                if s[iii] == t[j]:\n",
    "                    ans += num_distinct(iii + 1, j + 1)\n",
    "            ans_dict[key] = ans\n",
    "            return ans\n",
    "        return num_distinct(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        if m < n:\n",
    "            return 0\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m + 1):\n",
    "            dp[i][n] = 1\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == t[j]:\n",
    "                    dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i + 1][j]\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m,n = len(s),len(t)\n",
    "        # t 比s还要长 不可能s包含t\n",
    "        if n>m:return 0\n",
    "        dp = [[0]*(n+1) for i in range(m+1)]\n",
    "        # 初始化第一行，i=0 s是空串的情况 其实没必要直接是0 略过\n",
    "        # 初始化第一列，j=0, t是空串的情况，全部赋值为1\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s[i-1]==t[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][-1] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(m-1,-1,-1):\n",
    "                if t[j]==s[i]:\n",
    "                    dp[i][j] = dp[i+1][j+1]+dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i+1][j]\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        s_n =len(s)\n",
    "        t_n = len(t)\n",
    "        #dp[i][j] 是以i-1为结尾的s中有以j-1为结尾的t的t个数\n",
    "        dp = [[0 for _ in range(t_n+1)] for _ in range(s_n+1)]\n",
    "        #\n",
    "        for i in range(s_n):\n",
    "            dp[i][0]=1#把所有元素都删了，就有一个空字符串\n",
    "        for j in range(1,t_n+1):\n",
    "            dp[0][j] = 0#把所有元素都删了，就有一个空字符串\n",
    "\n",
    "        dp[0][0]=1#注意交集\n",
    "\n",
    "        #\n",
    "        for i in range(1,s_n+1):\n",
    "            for j in range(1,t_n+1):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] =dp[i-1][j]\n",
    "\n",
    "        #\n",
    "        # print(dp)\n",
    "\n",
    "        return dp[s_n][t_n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t):\n",
    "            return 0\n",
    "        memo = dict()\n",
    "        def dp(i, j):\n",
    "            nonlocal memo\n",
    "            key = '{}_{}'.format(i,j)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            if i <= -1 and j != -1:\n",
    "                # memo[key] = 0\n",
    "                return 0\n",
    "            if j == -1:\n",
    "                # memo[key] = 1\n",
    "                return 1\n",
    "            if s[i] != t[j]:\n",
    "                return dp(i-1, j)\n",
    "            res = dp(i-1, j-1) + dp(i-1, j)\n",
    "            memo[key] = res\n",
    "            return res\n",
    "        return dp(len(s)-1, len(t)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t):\n",
    "            return 0\n",
    "        memo = dict()\n",
    "        def dp(i, j):\n",
    "            nonlocal memo\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if i <= -1 and j != -1:\n",
    "                return 0\n",
    "            if j == -1:\n",
    "                return 1\n",
    "            if s[i] != t[j]:\n",
    "                return dp(i-1, j)\n",
    "            res = dp(i-1, j-1) + dp(i-1, j)\n",
    "            memo[(i,j)] = res\n",
    "            return res\n",
    "        return dp(len(s)-1, len(t)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        if len(s) < len(t):return 0\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if j == 0:return 1\n",
    "            if i == 0:return 0\n",
    "            if s[i - 1] == t[j - 1]:return dp(i - 1,j - 1) + dp(i - 1,j)\n",
    "            return dp(i - 1,j)\n",
    "        return dp(len(s),len(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        n=len(s)\n",
    "        m=len(t)\n",
    "        @cache\n",
    "        def g(i,j):\n",
    "            if i<0 and j>=0:\n",
    "                return 0\n",
    "            if i<0 or j<0:\n",
    "                return 1\n",
    "            if m-j>n-i:\n",
    "                return 0\n",
    "            res=0    \n",
    "            if s[i]==t[j]:\n",
    "               res=g(i-1,j-1)\n",
    "               \n",
    "            res+=g(i-1,j)\n",
    "            \n",
    "            return res\n",
    "        return g(len(s)-1,len(t)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == len(t):\n",
    "                return 1\n",
    "            if i == len(s):\n",
    "                return 0\n",
    "            if s[i] == t[j]:\n",
    "                return dfs(i + 1, j + 1) + dfs(i + 1, j)\n",
    "            return dfs(i + 1, j)\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        memo = dict()\n",
    "        def dp(i, j):\n",
    "            if j == n:\n",
    "                return 1\n",
    "            if i == m:\n",
    "                return 0\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "\n",
    "            if s[i] == t[j]:\n",
    "                memo[(i, j)] = dp(i + 1, j + 1) + dp(i + 1, j)\n",
    "                return memo[(i, j)]\n",
    "            else:\n",
    "                memo[(i, j)] = dp(i + 1, j)\n",
    "                return memo[(i, j)]\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def solve(i, j):\n",
    "            if j == len(t):\n",
    "                return 1\n",
    "            if i == len(s):\n",
    "                return 0\n",
    "            \n",
    "            if s[i] == t[j]:\n",
    "                return solve(i+1,j+1) + solve(i+1, j)\n",
    "            else:\n",
    "                return solve(i+1, j)\n",
    "        \n",
    "        return solve(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "\n",
    "        def process(s, index1, t, index2, dp):\n",
    "            if dp.get((index1, index2)) is not None:\n",
    "                return dp.get((index1, index2))\n",
    "            if index2 == len(t):\n",
    "                # 找到一个答案\n",
    "                return 1\n",
    "            if index1 == len(s):\n",
    "                # 遍历完 s 都未找到答案\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if s[index1] == t[index2]:\n",
    "                ans += process(s, index1 + 1, t, index2 + 1, dp)\n",
    "            ans += process(s, index1 + 1, t, index2, dp)\n",
    "            dp[(index1, index2)] = ans\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        dp = {}\n",
    "        for i in range(len(s) - len(t) + 1):\n",
    "            if s[i] == t[0]:\n",
    "                ans += process(s, i + 1, t, 1, dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "\n",
    "        @functools.cache        # Python functools记忆化模块，等价于哈希表记录的功能\n",
    "        def dfs(i, j):\n",
    "\n",
    "            if j == len(t):     # t匹配完了\n",
    "                return 1\n",
    "            if i == len(s):     # s匹配完了依然没找到答案\n",
    "                return 0\n",
    "            \n",
    "            cnt = 0\n",
    "            \n",
    "            # 跳过s[i]，并进行下一步搜索：s[i+1]与t[j]匹配\n",
    "            cnt += dfs(i+1, j)\n",
    "\n",
    "            # 选择s[i]，并进行下一步搜索\n",
    "            if s[i] == t[j]:    # 能选择s[i]的前提条件为：s[i] == t[j]\n",
    "                cnt += dfs(i+1, j+1)\n",
    "            \n",
    "            return cnt\n",
    "        \n",
    "        return dfs(0, 0)        # 初始从s[0]和t[0]开始搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "        # 计算s的子序列中t出现的次数\n",
    "\n",
    "        # 1. 递归： 选或不选，子集枚举\n",
    "        @cache\n",
    "        def dfs(i:int, j:int) -> int: # dfs(i,j) 表示s[0..i]在子序列t[0...j]中出现的次数\n",
    "            if j == len(t): return 1\n",
    "            if i == len(s): return 0\n",
    "            cnt = 0\n",
    "            cnt += dfs(i + 1, j) # 跳过s[i]，进行下一步搜索\n",
    "            if s[i] == t[j]: # 选择s[i]，进行下一步搜索\n",
    "                cnt += dfs(i + 1, j + 1)\n",
    "            return cnt \n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "        # 2. 迭代\n",
    "        # m, n = len(s), len(t)\n",
    "        # if m < n: return 0\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)] # s[0...i] 的子序列中 t[0...j]的出现次数\n",
    "        # for i in range(m + 1):\n",
    "        #     dp[i][n] = 1\n",
    "        \n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     for j in range(n - 1, -1, -1):\n",
    "        #         if s[i] == t[j]:\n",
    "        #             dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i + 1][j]\n",
    "        # return dp[0][0]\n",
    "\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
